package com.lw.leetcode.hash.c;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 30. 串联所有单词的子串
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/21 14:57
 */
public class FindSubstring {

    public static void main(String[] args) {
        FindSubstring test = new FindSubstring();

        // [0,9]
//        String str = "barfoothefoobarman";
//        String[] arr = {"foo", "bar"};

        // []
        String str = "wordgoodgoodgoodbestword";
        String[] arr = {"word", "good", "best", "word"};

        // [6,9,12]
//        String str = "barfoofoobarthefoobarman";
//        String[] arr = {"bar", "foo", "the"};

        List<Integer> substring = test.findSubstring(str, arr);

        System.out.println(substring);
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int m = words.length;
        int n = words[0].length();
        int size = n * m;
        int length = s.length();
        int l = length - n + 1;
        String[] arr = new String[l];
        for (int i = 0; i < l; i++) {
            arr[i] = s.substring(i, i + n);
        }
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.merge(word, 1, (a, b) -> a + b);
        }
        Map<String, Integer> items = new HashMap<>();
        for (int i = 0; i < length - size + 1; i++) {
            boolean flag = true;
            for (int j = 0; j < size; j += n) {
                String key = arr[i + j];
                Integer v = map.get(key);
                int c;
                if (v == null || v < (c = items.getOrDefault(key, 0) + 1)) {
                    flag = false;
                    break;
                }
                items.put(key, c);
            }
            items.clear();
            if (flag) {
                list.add(i);
            }
        }
        return list;
    }

}
